//Creates (first) derivative of the tree - builds new tree.
#include "Multitree.h"
#include "Diff.h"

namespace SymCe{

	Multitree * diff_tree(Multitree * tree, char * variable){
		//Creates first derivative of the tree using standard rules.
		//Derivative of a*b*c*... is sum a'*b*c*...+a*b'*c*...+a*b*c'*....+...
		//Derivative of 1/b is -1*b'/b^2 (that needs a huge tree...)
		Multitree * to_return = NULL;
		//Helpful constants. use: Multitree * something = copy_tree(&constant);
		Multitree zero;
		zero.childs = 0;
		zero.symbol.type = NUMBER;
		zero.symbol.number = 0;
		Multitree one;
		one.childs = NULL;
		one.symbol.type = NUMBER;
		one.symbol.number = 1;
		Multitree minusone;
		minusone.childs = NULL;
		minusone.symbol.type = NUMBER;
		minusone.symbol.number = -1;

		Multitree * argument = NULL;
		Multitree * dargument=NULL; 
		Multitree * cosin = NULL;
		//Multitree * minus = NULL;
		Multitree * two = NULL;
		Multitree * sinus = NULL;


		switch(tree->symbol.type){
			case NUMBER:
			case CONSTANT:
				//return zero.
				return copy_tree(&zero);
				break;

			case VARIABLE:
				if (strcmp(tree->symbol.name, variable) == 0){
					return copy_tree(&one);
				}else{
					return copy_tree(&zero);
				}
				break;

			case FUNCTION:
				dargument = diff_tree(tree->childs->subtree, variable);
				if ((dargument->symbol.type == NUMBER)
					&& (dargument->symbol.number == 0)){
						delete dargument;
						return copy_tree(&zero);
				}
				//dargument is ot zero. So we have to differentiate the function.
				argument = tree->childs->subtree; //copy it. It is just name.
				//f(x)' = x'*f'(x). x' is dargument, x is argument. to_return is * in between.
				to_return = new Multitree;
				to_return->symbol.type = OPERATOR;
				to_return->symbol.oper = MULTIPLY;
				to_return->childs = new ListOfChilds;
				to_return->childs->inverted = false;
				to_return->childs->next = NULL;
				to_return->childs->subtree = dargument;
				//to_return is dargument*(NULL). Now replace NULL with derivative of function.

				switch (tree->symbol.func){
					case SIN:
						cosin = new Multitree;
						cosin->symbol.type = FUNCTION;
						cosin->symbol.func = COS;
						cosin->childs = new ListOfChilds;
						cosin->childs->inverted = false;
						cosin->childs->next = NULL;
						cosin->childs->subtree = copy_tree(argument);
						to_return->childs->next=new ListOfChilds;
						to_return->childs->next->inverted = false;
						to_return->childs->next->next=NULL;
						to_return->childs->next->subtree = cosin;
						break;
					case COS:
						//derivative of cos is -sin.
						//So add to to_return sin(a) and then add there -1.
						//create sin(argument)
						sinus = new Multitree;
						sinus->symbol.type = FUNCTION;
						sinus->symbol.func = SIN;
						sinus->childs = new ListOfChilds;
						sinus->childs->inverted = false;
						sinus->childs->next = NULL;
						sinus->childs->subtree = copy_tree(argument);
						to_return->childs->next = new ListOfChilds;
						to_return->childs->next->inverted = false;
						to_return->childs->next->subtree = sinus;
						to_return->childs->next->next = new ListOfChilds; //here we put minus one.
						to_return->childs->next->next->next = NULL;
						to_return->childs->next->next->inverted = false;
						to_return->childs->next->next->subtree = copy_tree(&minusone);
						sort_tree(to_return);
						break;
						//der. of cos is -sin. So second child of to_return will be 0-cos(argument).
						/*
						minus = new Multitree;
						minus->symbol.type = OPERATOR;
						minus->symbol.oper = PLUS;
						minus->childs = new ListOfChilds;
						minus->childs->next = new ListOfChilds;
						minus->childs->next->inverted = true;
						minus->childs->next->next = NULL;
						minus->childs->next->subtree = copy_tree(argument);
						minus->childs->inverted = false;
						minus->childs->subtree = copy_tree(&zero);
						//minus is 0-argument.
						to_return->childs->next = new ListOfChilds;
						to_return->childs->next->next = NULL;
						to_return->childs->next->subtree = minus;
						to_return->childs->next->inverted = false;
						break;
						*/
					case LN:
						//deriv. of ln(x) is x'/x.
						to_return->childs->next = new ListOfChilds;
						to_return->childs->next->next = NULL;
						to_return->childs->next->inverted = true; //this is / in x'/x
						to_return->childs->next->subtree = copy_tree(argument);
						break;
					case TAN:
						//tan(a)' = a'/cos(a)^2
						cosin = new Multitree;
						cosin->symbol.type = FUNCTION;
						cosin->symbol.func = COS;
						cosin->childs = new ListOfChilds;
						cosin->childs->next = NULL;
						cosin->childs->inverted = false;
						cosin->childs->subtree = copy_tree(argument);
						two = new Multitree;
						two->childs = NULL;
						two->symbol.type = NUMBER;
						two->symbol.number = 2;
						Multitree * pow = new Multitree;
						pow->symbol.type = OPERATOR;
						pow->symbol.oper = POWER;
						pow->childs = new ListOfChilds;
						pow->childs->next = new ListOfChilds;
						pow->childs->next->next = NULL;
						pow->childs->next->inverted = false;
						pow->childs->next->subtree = two;
						pow->childs->inverted = false;
						pow->childs->subtree = cosin;
						to_return->childs->next = new ListOfChilds;
						to_return->childs->next->next = NULL;
						to_return->childs->next->inverted = true;
						to_return->childs->next->subtree = pow;
						break;
				}
				//Now we can just return to_return. 
				return to_return;
				break;

			case OPERATOR:
				//We will have to switch by the operator type.
				//PLUS is simple. Others are not that simple.
				//(a^b)' == e^(b*ln(a))' == e^(b*ln(a))*(b'*ln(a)+b*a'/a) -- if a != 0;
				//We can transform it to e^() and differentiate it then!
				//More often than not, some of these a, b, a' and b' are zeros and ones.
				//and multiplication is worst.
				//What about creating separate function?
				switch(tree->symbol.oper){
					case PLUS:
						return diff_plus(tree->childs, variable);
						break;
					case POWER:
						return diff_power(tree->childs, variable);
						break;
					case MULTIPLY:
						return diff_multiply(tree->childs, variable);
						break;
				}
				break;
		}
		//assert(false);
		return NULL;
	}

	Multitree * diff_plus(ListOfChilds * childs, char * variable){
		//Deriving PLUS is quite simple. Just differentiate all childs and put
		ListOfChilds * newchilds = NULL;
		Multitree * to_return;
		Multitree * diffed = NULL;
		ListOfChilds * added;
		while(childs != NULL){
			diffed = diff_tree(childs->subtree, variable);
			if ((diffed->symbol.type == NUMBER) && (diffed->symbol.number == 0)){
				childs = childs->next;
				delete_tree(diffed);
				diffed = NULL;
				continue;
			}
			added = new ListOfChilds;
			added->inverted = childs->inverted;
			added->subtree = diffed;
			added->next = newchilds;
			newchilds = added;
			childs = childs->next;
		}
		
		if(newchilds == NULL){
			to_return = new Multitree;
			to_return->childs = NULL;
			to_return->symbol.type = NUMBER;
			to_return->symbol.number = 0;
		}else{
			if(newchilds->next == NULL){
				if(!(newchilds->inverted)){
					to_return = newchilds->subtree;
					delete newchilds;
				}else{
					//return 0-(newchilds)
					to_return = new Multitree;
					to_return->symbol.type = OPERATOR;
					to_return->symbol.oper = PLUS;
					to_return->childs = new ListOfChilds;
					to_return->childs->inverted = false;
					//0
					to_return->childs->subtree = new Multitree;
					to_return->childs->subtree->childs = NULL;
					to_return->childs->subtree->symbol.type = NUMBER;
					to_return->childs->subtree->symbol.number = 0;
					to_return->childs->next = newchilds; //We do not have to invert it, because it already is.
				}
			}else{
				//We have enough childs to attach it to 
				to_return = new Multitree;
				to_return->childs = newchilds;
				to_return->symbol.type = OPERATOR;
				to_return->symbol.oper = PLUS;
			}
		}
		return to_return;
	}

	size_t count_childs(ListOfChilds * childs){
		size_t number = 0;
		while(childs!= NULL){
			number = number + 1;
			childs = childs->next;
		}
		return number;
	}


	Multitree * diff_multiply(ListOfChilds * childs, char * variable){
		//Derivative of a*b*c*... is sum a'*b*c*...+a*b'*c*...+a*b*c'*....+...
		//Derivative of 1/b is -1*b'/b^2 (that needs a huge tree...)
		//Derivation of multiplication is done in quadratic time :-)
		Multitree * diffed = NULL;
		ListOfChilds * for_multiplications = NULL;
		ListOfChilds * for_additions = NULL;
		Multitree * multiply = NULL; //There will be multiplications connected
		Multitree * processing = NULL;
		ListOfChilds * added = NULL;
		Multitree * to_return = NULL;
		//We can try to prune the tree during differentiation, but it seems to be quite difficult.
		//Let the tree be simplyfied after it is differentiated.

		ListOfChilds * outer_pass = childs;
		ListOfChilds * inner_pass = childs;
		while (outer_pass != NULL){
			bool minus = false;
			inner_pass = childs;
			//For every outer pass, we need to create new multiplication.
			for_multiplications = NULL;
			while(inner_pass != NULL){
				if(inner_pass != outer_pass){
					processing = copy_tree(inner_pass->subtree);
					added = new ListOfChilds;
					added->inverted = inner_pass->inverted;
					added->subtree = processing;
					added->next = for_multiplications;
					for_multiplications = added;
				}else{
					//We can get here only once in one outer cycle. We should probably check it.
					//TODO: Check how many times we get here in outer pass
					//Now we need to diff. it. If it is not inverted, then just diff. it. Otherwise add more childs.
					if(inner_pass->inverted){
						//1/a^2 to the for_multiplication and then add a' (it is comon for both inverted and not inverted)
						Multitree * pow = new Multitree;
						pow->symbol.type = OPERATOR;
						pow->symbol.oper = POWER;
						pow->childs = new ListOfChilds;
						pow->childs->next = new ListOfChilds;
						pow->childs->next->next = NULL;
						//Second child
						pow->childs->next->inverted = false;
						pow->childs->next->subtree = new Multitree;
						pow->childs->next->subtree->childs = NULL;
						pow->childs->next->subtree->symbol.type = NUMBER;
						pow->childs->next->subtree->symbol.number = 2;
						//First child (copy of inner_pass->subtree).
						pow->childs->inverted = false;
						pow->childs->subtree = copy_tree(inner_pass->subtree);
						//pow is now a^2;
						/*added = new ListOfChilds;
						added->inverted = false;
						added->subtree = new Multitree;
						added->subtree->childs = NULL;
						added->subtree->symbol.type = NUMBER;
						added->subtree->symbol.number = -1;
						added->next = for_multiplications;
						for_multiplications = added;
						//We added -1;
						*/
						//Why adding -1. We can just change inverted in additions.
						minus = true;

						//Now we add /a^2
						added = new ListOfChilds;
						added->inverted = true;
						added->subtree = pow;
						added->next = for_multiplications;
						for_multiplications = added;
					}
					//We add a' to for_multiplication (in all cases)
					processing = diff_tree(inner_pass->subtree, variable);
					added = new ListOfChilds;
					added->inverted = false;
					added->subtree = processing;
					added->next = for_multiplications;
					for_multiplications = added;
				}
				//Advance inner loop;
				inner_pass = inner_pass->next;
			}
			//We passed inner loop. Now we attach the result of it (for_multiplication) to the outer loop (for_addition)
			multiply = new Multitree;
			multiply->childs = for_multiplications;
			multiply->symbol.type = OPERATOR;
			multiply->symbol.oper = MULTIPLY;
			added = new ListOfChilds;
			added->subtree = multiply;
			added->inverted = minus;
			added->next = for_additions;
			for_additions = added;
			outer_pass = outer_pass->next;
		}
		diffed = new Multitree;
		diffed->symbol.type = OPERATOR;
		diffed->symbol.oper = PLUS;
		diffed->childs = for_additions;
		to_return = canonicalize_tree(diffed);
		delete_tree(diffed);
		return to_return;		
	}


	Multitree * diff_power(ListOfChilds * childs, char * variable){
		//(a^b)' == e^(b*ln(a))' == e^(b*ln(a))*(b'*ln(a)+b*a'/a) == a^b * (b'*ln(a) + b*a'/a) -- if a != 0;
		//And if a == 0? then just return 0.
		Multitree * to_return = NULL;
		if ((childs->subtree->symbol.type == NUMBER) && (childs->subtree->symbol.number == 0)){
			to_return = new Multitree;
			to_return->childs = NULL;
			to_return->symbol.type = NUMBER;
			to_return->symbol.number = 0;
			return to_return;
		}

		//Hope tat at least something is zero.
		Multitree * a = copy_tree(childs->subtree); //Will be copied where needed.
		Multitree * b = copy_tree(childs->next->subtree); //Will be copied where needed.
		//a and b should be deleted at the end of this function.
		Multitree * b_der = diff_tree(b, variable);
		Multitree * a_der = diff_tree(a, variable);
		//In any case, we need to create a^b part
		Multitree * pow = new Multitree;
		pow->symbol.type = OPERATOR;
		pow->symbol.oper = POWER;
		pow->childs = new ListOfChilds;
		pow->childs->next = new ListOfChilds;
		pow->childs->next->next = NULL;
		pow->childs->next->inverted = false;
		pow->childs->inverted = false;
		pow->childs->subtree = copy_tree(a);
		pow->childs->next->subtree = copy_tree(b);
		//a^b * (b'*ln(a) + b*a'/a)
		//We can now create the whole thing and then change it.
		//Or we can try to create only parts needed. But that means many ifs
		//Create the whole thing.
		Multitree * logarithm = new Multitree;
		logarithm->symbol.type = FUNCTION;
		logarithm->symbol.func = LN;
		logarithm->childs = new ListOfChilds;
		logarithm->childs->next = NULL;
		logarithm->childs->inverted = false;
		logarithm->childs->subtree = copy_tree(a);
		//logarithm is complete.
		Multitree * times1 = new Multitree;
		times1->symbol.type=OPERATOR;
		times1->symbol.oper = MULTIPLY;
		times1->childs = new ListOfChilds;
		times1->childs->next = new ListOfChilds;
		
		times1->childs->next->next = NULL;
		times1->childs->next->inverted = false;
		times1->childs->next->subtree = logarithm;
		
		times1->childs->inverted = false;
		times1->childs->subtree = copy_tree(b_der);
		//times1 is complete
		Multitree * times2 = new Multitree;
		times2->symbol.type = OPERATOR;
		times2->symbol.oper = MULTIPLY;
		//three childs.
		times2->childs = new ListOfChilds;
		times2->childs->next = new ListOfChilds;
		times2->childs->next->next = new ListOfChilds;
		//last
		times2->childs->next->next->next = NULL;
		times2->childs->next->next->inverted = true;
		times2->childs->next->next->subtree = copy_tree(a);
		//center
		times2->childs->next->inverted = false;
		times2->childs->next->subtree = copy_tree(a_der);
		//first
		times2->childs->inverted = false;
		times2->childs->subtree = copy_tree(b);
		//plus
		Multitree * plus = new Multitree;
		plus->symbol.type = OPERATOR;
		plus->symbol.oper = PLUS;
		plus->childs = new ListOfChilds;
		plus->childs->next = new ListOfChilds;
		plus->childs->next->next = NULL;
		plus->childs->inverted = false;
		plus->childs->next->inverted = false;
		plus->childs->next->subtree = times2;
		plus->childs->subtree = times1;
		//plus is complete. Now connect it with pow with Multiplication and we are ready to return it.
		to_return = new Multitree;
		to_return->symbol.type = OPERATOR;
		to_return->symbol.oper = MULTIPLY;
		//two childs. first is pow, second is plus.
		to_return->childs = new ListOfChilds;
		to_return->childs->next = new ListOfChilds;
		//second
		to_return->childs->next->next = NULL;
		to_return->childs->next->inverted = false;
		to_return->childs->next->subtree = plus;
		to_return->childs->inverted = false;
		to_return->childs->subtree = pow;
		//Finished.
		delete_tree(a);
		delete_tree(b);
		delete_tree(a_der);
		delete_tree(b_der);
		return to_return;
	}



		



			

}

